

//class Node{
//    int val; //数据域
//    Node left; //左孩子的引用，常常代表左孩子为根的整颗左子树
//    Node right; //右孩子的引用，常常代表右孩子为根的整颗右子树
//}
//
//class Node{
//    int val; //数据域
//    Node left; //左孩子的引用，常常代表左孩子为根的整颗左子树
//    Node right; //右孩子的引用，常常代表右孩子为根的整颗右子树
//    Node parent; //当前节点的根节点
//}

//相同的树
//class Solution {
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(q == null && p == null){
//            return true;
//        }
//        if(q== null && p != null || q!= null && p == null){
//            return false;
//        }
//        if(p.val != q.val){
//            return false;
//        }
//        return isSameTree(q.left, p.left) && isSameTree(q.right, p.right);
//    }
//}

//另一颗子树
//class Solution {
//    public boolean isSameTree(TreeNode root, TreeNode subRoot) {
//        if(subRoot == null && root == null){
//            return true;
//        }
//        if(subRoot== null && root != null || subRoot!= null && root == null){
//            return false;
//        }
//        if(root.val != subRoot.val){
//            return false;
//        }
//        if(root == null){
//            return false;
//        }
//        return isSameTree(subRoot.left, root.left) && isSameTree(subRoot.right, root.right);
//    }
//
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        if(root == null)return false;
//        boolean ist = isSameTree(root, subRoot);
//        if (ist){
//            return true;
//        }
//        if(isSubtree(root.left, subRoot)){
//            return true;
//        }
//        if(isSubtree(root.right, subRoot)){
//            return true;
//        }
//        return false;
//    }
//}

//翻转二叉树
//class Solution {
//    public TreeNode invertTree(TreeNode root) {
//        if(root == null){
//            return null;
//        }
//        TreeNode tmp = root.left;
//        root.left = root.right;
//        root.right = tmp;
//        invertTree(root.left);
//        invertTree(root.right);
//        return root;
//    }
//}
